'''
https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-interview-150
'''
from typing import List


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m,n = len(grid), len(grid[0])
        def f(i, j):
            if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
                grid[i][j] = '0'
                f(i+1, j)
                f(i-1, j)
                f(i, j+1)
                f(i, j-1)
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    res += 1
                    f(i, j)
        return res